class Solution {
public:
    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int num) {
        if (num == 0)
            return;
        B.push_back(A[0]);
        if (A.size())
            C.push_back(A[0]);
        A.erase(A.begin());

        if (!B.size())
            C.push_back(B[0]);
        dfs(A, B, C, num - 1);
    }
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int num = A.size();
        dfs(A, B, C, num);
    }
};
//算法原理：
//n=1时，直接把唯一的盘子放到柱子3即可
//n=2时，想的是把最大的盘子转到C柱子，首先得利用小盘子放在柱子B
//n=3时，想的是把最大得盘子转到C柱子，首先得把上面两个盘子放到柱子B，如何放参考n=2
//n=4时，想的是把最大的盘子转到C柱子，则把上面三个盘子放到柱子B，如何放参考n=3
//。。。以此类推